/*
 * OrderedBinaryRelation.h
 *
 *  Created on: 01/09/2012
 *      Author: marcio
 */

#ifndef ORDEREDBINARYRELATION_H_
#define ORDEREDBINARYRELATION_H_

#include "OrderedSet.h"

/*!\class OrderedPair
 * \brief A ordered pair contain two elements
 *
 * Each Object of this class represents a ordered pair (x,y) of
 * elements of the type especified by the template
 *
 *\tparam T the type of the elements
 * **/
template<typename T>
class OrderedPair{
private:
	T x;//!< the first element in the ordered pair
	T y;//!< the second element in the ordered pair

public:
	/*!
	 * \brief Contructor
	 *
	 * A simple constructor to allocate the memory necessary to a
	 * object of this class
	 */
	OrderedPair(){};

	/*!
	 * \brief Construtor
	 *
	 * Create a ordered pair with first element being a and the second
	 * being b.
	 *
	 * Notice that, as the pair is a ordered one, the order of the parameters
	 * is important. The pair (a,b) is different of (b,a)
	 *
	 * \param a the first element of the par
	 * \param b the second element of the par
	 * */
	OrderedPair(T a, T b){x = a; y = b;};

	/*!
	 * \brief Retrieve the first element of the object.
	 *
	 * \return the first element of the object.
	 * */
	T getX(){return x;};

	/*!
	 * \brief Retrieve the second element of the object
	 *
	 * \return the second element of the object
	 * */
	T getY(){return y;};

	/*!
	 * \brief Change the first element of the object
	 *
	 * */
	void setX(T a){x = a;};

	/*!
	 * \brief Change the second element of the object
	 *
	 * */
	void setY(T b){y = b;};

	/*!
	* \brief Operator =
	*
	* Overwrite the commun operator=.
	*
	* The mean of the operation (a,b) = (x,y) is that
	* a will receive x and b will receive y.
	*
	* Again, notice that the order is important.
	*/
	OrderedPair<T> operator=(OrderedPair<T> a){
		x = a.x;
		y = a.y;
		return *this;
	}

	/*!
	 * \brief Operator ==
	 *
	 * Overwrite the commun operator==.
	 *
	 * (a,b) == (x,y) if and only if a is equal to x and b is equal to y
	 *
	 * Again, notice that the order is important.
	 */
	bool operator==(OrderedPair<T> a){
		return (x == a.x) && (y == a.y);
	}

	/*!
	 * \brief Operator !=
	 *
	 * Overwrite the commun operator==.
	 *
	 * (a,b) != (x,y) is false if and only if a is equal to x and b is equal to y,
	 * otherwise it will be true.
	 *
	 * Again, notice that the order is important.
	 */
	bool operator!=(OrderedPair<T> a){
		return !((x == a.x) && (y == a.y));
	}

};

/*!\class OrderedBinaryRelation
 *
 * \brief A Binary Relation with a specified order between to elements and two pairs of elements
 *
 * A Binary Relation in a universe with a specified order between the elements of the
 * universe and between the pairs of elements. usually the order used to implement this
 * class is a lexicographic order based in the one applied to the elements in the universe.
 *
 * The binary relation can be viewed as a set of pairs of the universe. For this reason
 * this class is a orderedSet as well. Again the order between pairs of elements is dependent of
 * each implementation of this abstract class.
 *
 * The universe is determined in each implementation as well. Notice that the universe determined are the set
 * of valid ELEMENTS to make pairs not the valid pairs. The real universe of this object are
 * ALL the pair composed by elements of the universe determined in each implementation.
 *
 * */
template<typename T>
class OrderedBinaryRelation: DirectlyAddressedSet<OrderedPair<T> >{
protected:

	/*!
	 * \brief Basic constructor
	 *
	 * used to allocate memory for a object of this class
	 */
	OrderedBinaryRelation(){};
public:

	/*!
	 * \brief Add a pair to the binary relation represented by this element.
	 *
	 * Add a pair to the binary relation represented by this object. if the pair is composed by
	 * a element to in the universe, it will cause a error.
	 *
	 * The same as add(par.getX(), par.getY()).
	 *
	 * \param the pair to be added to the object.
	 *
	 * \return true if the pair is added and false otherwise.
	 * \see add()
	 * */
	virtual bool add(OrderedPair<T> par);

	/*!
	 * \brief Remove a pair to the binary relation represented by this element.
	 *
	 * Remove a pair to the binary relation represented by this object. if the pair is composed by
	 * a element to in the universe, it will cause a error.
	 *
	 * The same as remove(par.getX(), par.getY()).
	 *
	 * \param the pair to be removed to the object.
	 *
	 * \return true if the pair is removed and false otherwise.
	 *
	 * \see remove()
	 * */
	virtual bool remove(OrderedPair<T> par);

	/*!
	 * \brief Add a pair to the binary relation represented by this element.
	 *
	 * Add a pair to the binary relation represented by this object. The pair is composed
	 * by the two elements passed as parameter to the function.
	 *
	 * If one of the elements are not in the universe a error will occur. This method
	 * must be implement in each child concrete class because depends on the the
	 * data structure.
	 *
	 * \param x the first element of the pair.
	 * \param y the second element of the pair.
	 *
	 * \return true if the pair is added and false otherwise.
	 * */
	virtual bool add(T x, T y) = 0;

	/*!
	 * \brief Remove a pair to the binary relation represented by this element.
	 *
	 * Remove a pair to the binary relation represented by this object. The pair is composed
	 * by the two elements passed as parameter to the function.
	 *
	 * If one of the elements are not in the universe a error will occur. This method
	 * must be implement in each child concrete class because depends on the the
	 * data structure.
	 *
	 * \param x the first element of the pair.
	 * \param y the second element of the pair.
	 *
	 * \return true if the pair is removed and false otherwise.
	 * */
	virtual bool remove(T x, T y) = 0;

	/*!
	 * \brief Return a set of the elements that make pair with the specified one in the
	 * relation where the specified element is the first element.
	 *
	 * Return a set \f$ C \f$ of all the elements of the universe such that in the current
	 * state of the object make a pair with the specified one.
	 *
	 * More precisely \f$ C =\{u \mid (elem, u) \in R \}\f$ where R is the binary relation
	 * represented by this object.
	 *
	 * Notice that the order is very important here. The elements in *C* must be the
	 * seconds in the pair.
	 *
	 * \param elem the specified element
	 *
	 * \return the image set of elem. The set of all elements u such that (elem,u) belongs
	 * to the relation.
	 * */
	virtual DirectlyAddressedSet<T>* image(T elem) = 0;

	/*!
	 * \brief Return a set of the elements that make pair with the specified one in the
	 * relation where the specified element is the second element.
	 *
	 * Return a set \f$ C \f$ of all the elements of the universe such that in the current
	 * state of the object make a pair with the specified one.
	 *
	 * More precisely \f$ C =\{u \mid (u, elem) \in R \}\f$ where R is the binary relation
	 * represented by this object.
	 *
	 * Notice that the order is very important here. The elements in *C* must be the
	 * firsts in the pair.
	 *
	 * \param elem the specified element
	 *
	 * \return the image set of elem. The set of all elements u such that (u,elem) belongs
	 * to the relation.
	 * */
	virtual DirectlyAddressedSet<T>* inverse(T elem) = 0;

	/*!
	 * \brief Verify if the relation is transitive
	 *
	 * Verify if the relation is transitive. A relation is transitive if for
	 * all pairs (u,v) and (v,z) in the relation, pair (u,z) is in the relation
	 * as well
	 *
	 * \return true if the relation represented by this object is transitive and
	 * false otherwise.
	 * */
	virtual bool isTransitive() = 0;

	/*!
	 * \brief Verify if the relation is reflexive
	 *
	 * Verify if the relation is reflexive. A relation is reflexive if for
	 * all element u of the universe the pair (u,u) is in the relation.
	 *
	 * \return true if the relation represented by this object is reflexive and
	 * false otherwise.
	 * */
	virtual bool isReflexive() = 0;

	/*!
	 * \brief Verify if the relation is empty
	 *
	 * Verify if the relation is empty, has no pair at all. This information depends on the
	 * data structure used to implement this class, so each child concrete class
	 * must implement this method.
	 *
	 * \return true if the relation represented by this object is empty and
	 * false otherwise.
	 * */
	virtual bool isEmpty() = 0;

	/*!
	 * \brief Verify if the relation is simetric
	 *
	 * Verify if the relation is simetric. A relation is simetric if for
	 * all pair (u,v) in the relation, the pair (v,u) is in the relation
	 * as well.
	 *
	 * \return true if the relation represented by this object is simetric and
	 * false otherwise.
	 * */
	virtual bool isSimetric() = 0;

	/*!
	 * \brief Verify if the relation is antisimetric
	 *
	 * Verify if the relation is antisimetric. A relation is antisimetric if for
	 * all pair (u,v) in the relation, the pair (v,u) is not in the relation
	 * as well.
	 *
	 * \return true if the relation represented by this object is antisimetric and
	 * false otherwise.
	 * */
	virtual bool isAntiSimetric() = 0;

	/*!
	 * \brief The number of pairs in wich the specified element is the first element.
	 *
	 * Return the cardinality of the set returned by reverse(elem).
	 *
	 * \param elem the specified element
	 *
	 * \return the number of pairs in which elem is the first element.
	 *
	 * \see reverse().
	 * */
	virtual long degreeIn(T elem) = 0;

	/*!
	 * \brief The number of pairs in wich the specified element is the second element.
	 *
	 * Return the cardinality of the set returned by image(elem).
	 *
	 * \param elem the specified element
	 *
	 * \return the number of pairs in which elem is the second element.
	 *
	 * \see reverse().
	 * */	virtual long degreeOut(T elem) = 0;
};

template<typename T>
inline bool OrderedBinaryRelation<T>::add(OrderedPair<T> par){
	return add(par.getX(), par.getY());
}

template<typename T>
inline bool OrderedBinaryRelation<T>::remove(OrderedPair<T> par){
	return remove(par.getX(), par.getY());
}


#endif /* ORDEREDBINARYRELATION_H_ */
